// 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
// 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
// 字符串的子序列是原始字符串删除一些（或不删除）字符，不改变剩余字符相对位置的新字符串
// 五部曲

// 1. 确定dp数组的含义，`dp[i][j]`，代表下标i-1结尾的字符串s，和下标j-1结尾的字符串t，相同子序列的长度
// 2. 确定递推公式
// ```js
// if(s[i-1] === t[j-1]) {
//     dp[i][j] = dp[i-1][j-1] + 1
// } else {
//     dp[i][j] = dp[i][j-1] // 相当于看s[i-1]和t[j-2]的比较结果
// }
// ```
// 3. dp数组初始化，`dp[0][0]和dp[i][0]都初始化为0`
// 4. 遍历顺序为从上到下，从左到右
// 5. 举例推导

// 时间复杂度：O(n × m)
// 空间复杂度：O(n × m)

function isSubsequence(s, t) {
    let dp = new Array(s.length + 1).fill(0).map(_ => new Array(t.length + 1).fill(0))
    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= t.length; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = dp[i][j - 1]
            }
        }
    }
    return dp[s.length][t.length] === s.length
}

let s = "abc", t = "ahbgdc"
console.log(isSubsequence(s, t))

var isSubsequence = function (s, t) {
    let i = 0,
        j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] == t[j]) i++;
        j++;
    }
    return i == s.length;
};
